
# from itertools import combinations
# from collections import defaultdict
# def apriori(data, min_support):
#
#     def generate_candidates(prev_freq_itemsets, k):
#         candidates = set()
#         itemsets = list(prev_freq_itemsets)
#         for i in range(len(itemsets)):
#             for j in range(i + 1, len(itemsets)):
#                 union = itemsets[i] | itemsets[j]
#                 if len(union) == k:
#                     candidates.add(union)
#         return candidates
#
#     # 1
#     item_support = defaultdict(int)
#     for transaction in data:
#         for item in transaction:
#             item_support[frozenset([item])] += 1
#
#     frequent_itemsets = {k: v for k, v in item_support.items() if v >= min_support}
#     all_frequent_itemsets = dict(frequent_itemsets)
#
#     k = 2
#
#     while frequent_itemsets:
#         # 2
#         candidates = generate_candidates(frequent_itemsets.keys(), k)
#
#         # 3
#         candidate_support = defaultdict(int)
#         for transaction in data:
#             for candidate in candidates:
#                 if candidate.issubset(transaction):
#                     candidate_support[candidate] += 1
#
#         # 4
#         frequent_itemsets = {k: v for k, v in candidate_support.items() if v >= min_support}
#         all_frequent_itemsets.update(frequent_itemsets)
#         k += 1
#
#     return all_frequent_itemsets
#
# transactions = [
#     {'milk', 'bread', 'butter'},
#     {'beer', 'bread', 'butter', 'milk'},
#     {'milk', 'bread'},
#     {'beer', 'bread'},
#     {'milk', 'bread', 'butter', 'beer'}
# ]
#
# min_support_threshold = 2
# frequent_itemsets = apriori(transactions, min_support_threshold)
#
# print("Frequent Itemsets and their Supports:")
# for itemset, support in frequent_itemsets.items():
#     print(f"{set(itemset)}: {support}")